Окский парк расположен в историческом центре древнего Мурома. Это одно из любимейших мест отдыха горожан. Именно отсюда начинался наш город. По данным археологии здесь выявлены слои X в., что свидетельствует о древности этого места. До прихода в Муром славян на территории современного Окского парка находилось поселение племени мурома, давшее впоследствии городу своё наименование. Нижние слои культурного слоя, находящиеся на глубине четырех метров, содержат лепную керамику «муромского типа», поделки из кости, большое количество костей домашних животных, зерен проса. Выше располагался древнерусский слой домонгольского времени с гончарной керамикой «курганного типа», которая датируется XI-XIII вв. В этом слое находятся следы меднолитейного и косторезного ремесел, указывающие на городской характер культурных отложений.
Среди находок в слоях X - первой половины XIII в. найдены лепная и гончарная древнерусская посуда, многочисленные и разнообразные инструменты ремесленников, бытовые предметы, украшения. Найдено много предметов восточного импорта: украшения из сердолика, хрусталя, лазурита, поливная керамика среднеазиатского происхождения, лощеная посуда из Волжской Болгарии, разнообразные бусы. О связях с Византией свидетельствуют находки амфор, стеклянных расписных браслетов. Ещё в 1873 г. при реставрации ныне утраченного собора «Рождество Богородицы» были сделаны уникальны находки архитектурных деталей XII в. (обломки полуколонн и капителей). Это свидетельствует о наличии в XII в. в центральной части Мурома белокаменного храма и существовавшем в городе камнеобрабатывающем ремесле. В 1868 г. на территории современного Окского парка был найден уникальный клад восточных монет, датированные 715-935 гг.
Наиболее крупные по масштабам археологические работы на территории современного Окского парка проводились в 1982-1987 гг. Было исследовано около 200 кв. м. Среди находок следует отметить стеклянные браслеты – излюбленное украшение древнерусских горожанок, шиферные пряслица. Находки в раскопанных усадьбах свидетельствуют о том, что они принадлежали зажиточным горожанам. В древнерусском горизонте культурного слоя выявлены следы больших пожаров. Ранний из них был связан с одним из набегов на Муром волжских болгар в XI в. Другие пожары – следствие татаро-монгольских погромов. В культурных отложениях второй половины XIII – начала XVI в. обнаружены остатки наземных построек срубной конструкции, с глинобитными печами.
В средние века территория современного Окского парка – административный, политический, духовный и военный центр Мурома. Здесь до конца XVIII в. находилась деревянная крепость – городской кремль, защищавшая жителей города от многочисленных врагов. На его территории стоял главный храм Мурома – Собор Рождества Богородицы, разобранный в 1930-е гг. Главной святыней собора считались мощи муромских святых Петра и Февронии (ныне находятся в Троицком женском монастыре г. Мурома).
Кремль (он же детинец или крепость) – обязательная принадлежность любого средневекового города. Вплоть до середины XVI г. Муром считался пограничным городом Русского государства. Кремль в Муроме всегда был деревянным, т.к. каменные постройки были очень дорогостоящими и сложными в возведении. В XVII в. муромский кремль выглядел следующим образом. На высокой горе (она называлась Воеводской, т.к. внутри крепости находился двор воеводы) в форме неправильного четырехугольника стояли деревянные стены. В городе имелось две проездные башни, одна тайницкая и одиннадцать глухих (т.е. непроезжих) башен. Одна проездная угловая башня (южная) назвалась Спасской, т.к. от неё начиналась дорога в Спасский монастырь; противоположная (северо-западная) – Базарная. Последняя получила название от городского торга – базара, раскинувшегося сразу за крепостью. Была в муромской крепости и Тайницкая башня. Находилась она напротив Николо-Набережной церкви. Тайник представлял собой вырытый из-под городовой стены ход. В конце этого тайника был устроен колодец с водой. В XVII в. стены и башни муромского кремля были срублены из дубового и соснового леса. Они тянулись вокруг города на 552 сажени (около 1,5 км). В стенах муромского кремля были устроены бойницы в три ряда. Они позволяли вести успешную оборону.
В первой половине XVII в. муромский кремль имел очень плотную застройку. По описи 1636 г. на его территории находилось 113 дворов, возведенных «для осадного времени». Владельцами этих дворов были именитые князья и бояре (Иван Никитич Романов, Борис Михайлович Лыков, Иван Борисович Черкасский, Иван Петрович Шереметьев и др.), рядовые дворяне (Борисовы, Осорьины, Аристовы, Киселевы, Апраксины, Кравковы и др.), а также духовенство, посадские люди и даже крестьяне. Имели свои осадные дворы и монастыри (Спасский, Благовещенский, Троице-Сергиев, Борисоглебский).
Частые пожары, недолговечность деревянных стен препятствовали сохранению крепости. Муромский кремль просуществовал до 2-й половины XVIII в. Согласно описанию, составленному в 1764 г., он находился в полуразвалившемся состоянии. После сильного пожара, произошедшего во второй половине XVIII в., крепость больше не восстанавливалась. После упразднения муромского кремля, что отчасти было связано с отсутствием военной угрозы, на его обширной территории разбили ярморочную площадь. Здесь раз в год проходила оживленная муромская ярмарка, приуроченная ко дню памяти Петра и Февронии (25 июня по старому стилю). Там же, под стенами древнего собора, в субботние дни проводилась регулярная базарная торговля.
В середине XIX в. по ряду причин (прежде всего, по пожарным и санитарным), ярмарку из центра города перенесли на городскую окраину. В 1852 г. на средства муромского городничего, князя Ивана Алексеевича Трубецкого, устроили городской бульвар и беседку. Бульвар содержался на средства города. Так, в 1857 г. на ремонт бульвара и содержания сторожа было потрачено из городской казны 50 руб.
К 1870-м гг. галерея бульвара пришла в ветхость. 11 апреля 1874 г. на заседании муромской городской Думы поднимался вопрос о необходимости постройки новой ротонды, так как старая «пришла в совершенную ветхость и грозит падением». Посовещавшись, Дума решила выделить на строительство 500 руб. Впоследствии, чтобы избавиться от лишних расходов, помещения веранды неоднократно сдавались в аренду под всевозможные клубы и питейные заведения. Например, 12 мая 1882 г. муромский купец В.Ф. Львицын получил разрешение построить на городском бульваре новые павильоны для торговли минеральной водой.
Летом на Окском бульваре играл духовой оркестр. В 1913 г. на эти цели было отпущено 180 руб. из городской казны. С наступлением теплых дней на бульвар перемещался клуб муромского Общественного собрания. В 1914 г. строительное отделение Владимирского губернского правления разрешило администрации города расширить городской бульвар, ставший к тому времени излюбленным местом проведения досуга горожан. Именно территория городского бульвара была электрифицирована одной из первых в далеком 1914 г.
В начале 1920-х гг. вход на территорию Окского бульвара был платным. Входной билет стоил 200 тыс. руб. по ценам того времени.
Весной 1924 г. на бывшей соборной площади разбили сквер. Обширный участок окружили изгородью и озеленили. Тогда же в Окском саду с 17 до 22 ч. функционировала библиотека-читальня.
На сцене летнего театра Окского сада проводились регулярные выступления театральных и музыкальных коллективов. В июле 1924 г. муромская публика тепло принимала известного балалаечника-виртуоза Б.С. Трояновского – организатора и первого руководителя Московского Великорусского оркестра народных инструментов.
В 1920-30-е гг. под стенами древнего собора была разбита спортивная площадка, где регулярно проходили городские соревнования.
В послевоенные годы на территории Окского парка (тогда он официально назывался «Парк им. В.И. Ленина») стали сооружать аттракционы. Здесь же не одно десятилетие функционировала танцевальная площадка.
В 1965 г. на восточной окраине Окского парка устроили новую смотровую площадку. С неё открывается великолепный вид на заокские дали.
В 1986 г. в честь 40-летия Победы в Великой Отечественной войне на территории парка установили бюсты муромцам - Героям Советского Союза. Так на территория Окского парка появилась ещё одна местная достопримечательность – Аллея Героев.
В 1999 г. в Окском парке установили высокий 21-метровый памятник Илье Муромцу (скульптор В.М. Клыков, архитектор Н.А. Беспалов), ставший новым символом былинного города.
Прошли годы, но по-прежнему в Окский парк идут горожане и гости древнего Мурома, чтобы провести свой досуг и полюбоваться прекрасным видом заокских далей. Территория парка благоустраивается, становится краше год от года. Здесь регулярно проходят городские мероприятия, встречи выпускников, торжества, приуроченные ко Дню города. К памятнику Илье Муромцу тянутся многочисленные туристы, возлагают цветы молодожены.